package algorthm.systemTraning.mergeSort.smallNumber;

/**
 * @className: SamllNumber
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/14 14:33
 */
public class SmallNumber {
    public static int smallNumber = 0 ;
    public static int dgCount = 0 ;
    public static int[] merge(int[] array1 , int[] array2){
        int i1 = 0 , i2 = 0 , i3 = 0;
        int[] ans = new int[array1.length + array2.length];
        while(i1 < array1.length && i2 < array2.length){
            if(array1[i1] >= array2[i2]){
                ans[i3++] = array2[i2++];
            }else{
                smallNumber += array1[i1]*(array2.length - i2);
                ans[i3++] = array1[i1++];
            }
        }

        while(i1 < array1.length){
            ans[i3++] = array1[i1++];
        }

        while(i2 < array2.length){
            ans[i3++] = array2[i2++];
        }
        return ans ;
    }
    public static int[] mergeSort(int[] array , int L , int R){
        dgCount++;
        int[] ans = null ;
        if(L == R){
            ans = new int[1];
            ans[0] = array[L];
            return ans ;
        }
        int mid = (L + R) >> 1 ;
        int[] left = mergeSort(array , L , mid);
        int[] right = mergeSort(array , mid + 1 , R);
        return merge(left , right);
    }
    public static void main(String[] args) {

    }
}
